function Node(value){
    this.value = value;
    this.passCount = 0;
    this.endCount = 0;
    this.children = new Array(75);
  }
class Trie {
    constructor(){
        this.root = new Node(null);
    }
    insert(word){
        if(!word){
        return;
        }
        var cur = this.root;
        for(var i = 0; i < word.length; i++){
        var c = word[i];
        if( !cur.children[c] ){
            cur.children[c] = new Node(word[i]);
        }
        cur = cur.children[c];
        cur.passCount++; // 有多个字符串经过此结点
        }
        cur.endCount++; // 有多个字符串在这里结束
    }
    // remove(word) {
    //     var cur = this.root, array = [], n = word.length;
    //     for (var i = 0; i < n; i++) {
    //       var c = word[i];
    //       var node = cur.children[c];
    //       if (node) {
    //         array.push(node);
    //         cur = node;
    //       } else { // 如果缺少word的某个字符，立即返回
    //         return false;
    //       }
    //     }
    //     // word可能包含已有的某个字符串，也算不命中，此时array.length > n
    //     if (array.length === n) {
    //       var parent = this.root;
    //       cur.endCount--;
    //       array.forEach(function (el) {
    //         el.passCount--;// 减1
    //         if (!el.passCount) {// 减到零则从父结点删掉此字符串
    //           delete parent.children[el.value];
    //         }
    //         parent = el;
    //       });
    //     } else {
    //       return false;
    //     }
    // }
    search(word, cb) { // 收集命中的结点，并交给回调进一步处理
        var cur = this.root, array = [], n = word.length;
        for (var i = 0; i < n; i++) {
          var c = word.charCodeAt(i) - 33;
          var node = cur.children[c];
          if (node) {
            array.push(node);
            cur = node;
          } else { // 如果缺少word的某个字符，立即返回
          return false;
          }
        }
        return cb(cur, array);
    }
    isContainWord(word){ // 是否包含某个字符串
        return this.search(word, function (last) {
          return last.endCount;
        });
    }
    remove(word, cb) { // 移除字符串
        var root = this.root;
        return this.search(word, function (last, array) {
          if (array.length === word.length) {
            var parent = root;
            last.endCount--;
            array.forEach(function (el) {
              el.passCount--;// 减1
              if (!el.passCount) {// 减到零则从父结点删掉此字符串
                delete parent.children[el.value];
              }
              parent = el;
            });
          }
        });
    }
    isContainPrefix(word){ // 是否包含某个字符串的前缀
        return this.search(word, (last) =>{
          return last !== this.root;
        });
    }
    CountWord(word) {
        // 统计某字符串出现次数的方法
        return this.search(word, (last) =>{
          return last.endCount;
        }) || 0; // 处理false
    }
    countWord(word) {
        // 统计某字符串出现次数的方法
        return this.search(word, (last) =>{
          return last.passCount;
        }) || 0; // 处理false
    }
    // getSortedArray() {
    //     this.root.value = ''; // 根结点的value为null时要处理一下
    //     function collect(node, cb, str) {
    //       var nextStr = str + node.value;
    //       if (node.endCount) {
    //         cb(nextStr);
    //       }
    //       for (var i in node.children) {
    //         collect(node.children[i], cb, nextStr);
    //       }
    //     }
    //     var array = [];
    //     collect(this.root, function (str) {
    //       array.push(str);
    //     }, "");
    //     return array;
    // }
    getSortedArray() {
        this.root.value = ''; // 根结点的value为null时要处理一下
        function collect(node, cb, str) {
          var nextStr = str + node.value;
          if (node.endCount) {
            for(let i = 0; i < node.endCount; i++){
              cb(nextStr);
            }
          }
          for (let i in node.children) {
            collect(node.children[i], cb, nextStr);
          }
        }
        var array = [];
        collect(this.root, function (str) {
          array.push(str);
        }, "");
        return array;
    }
    longestCommonPrefix() { 
        var cur = this.root, lcp = '',wordsCount = 0;
        while (true) {
          var count = 0;
          var kids = cur.children;
          for (var i in kids) {
            // 处理数组原型链被污染的问题，防止这是一个polyfill添加的方法名
            // 而不是一个整数类型的值
            if (cur.children.hasOwnProperty(i)) { // cur.children.hasOwnProperty(i)也可以
              count++;
            }
          }
          console.log(count, 'aa');
          // 如果这个父结点只有一个孩子，说明没有分叉
          if (count === 1) {
            cur = kids[i];
            // 根结点的独生子的passCount，就是插入字符串的总数量，只计算一次
            if (!wordsCount) {
              wordsCount = cur.passCount;
            }
            if (cur.passCount == wordsCount) {
              // 由于是共同前缀，要保证所有字符串都经过这个结点
              lcp += cur.value;
              continue; // 继续搜索下一个结点
            }
            break;
          } else break;
        }
        return lcp;
    }
    searchRecursively( cur, word, index){
        if(index == word.length) {
          return cur.endCount;
        }
        var c = word.charAt(index);
        if(c=='*'){
          for(var i in cur.children){ // 下一层
            if(searchRecursively(cur.children[i], word,index+1)){
              return true;
            } 
          }
          return false;
        }else{
          var node = cur.children[c.charCodeAt(0) - 33];
          if(node){
            return searchRecursively(node,word,index+1);
          }else{
            return false;
          }
        }
        return false;
      }
      
      fuzzySearch(word){
        return searchRecursively(this.root, word, 0);
      }
  }
  
//   var t = new Trie(); // test
//   t.insert("I");
//   t.insert("Love");
//   t.insert("China");
//   t.insert("China");
//   t.insert("Ch");
//   console.log(t);
// var a = new Array(75);
// a[7] = 7;
// a[8] = 8;
// a[4] = 4;
// a[2] = 2;
// for (var i in a) {
//   console.log(i);
// }
// // 输出2，4，7，8

// test
// var trie = new Trie();
// trie.insert("I");
// trie.insert("Love");
// trie.insert("China");
// trie.insert("rubylouvre");
// trie.insert("rubylouvre");
// trie.insert("man");
// trie.insert("handsome");
// trie.insert("love");
// trie.insert("Chinaha");
// trie.insert("her");
// trie.insert("know");
// var array = trie.getSortedArray();
// console.log(array, '!!');

var trie = new Trie();
trie.insert("flowersbfldbfh");
trie.insert("flow");
trie.insert("");

console.log(trie.longestCommonPrefix(), '!!');// fl 